1. Field of the Invention
The present invention relates to a method and an apparatus to optimize resource usage in a scheduled testing system, and more particularly, to a method and an apparatus to optimize resource usage in a scheduled software testing system that is required to use limited physical resources.
2. Description of the Related Art
A scheduled software testing system is one in which software tests are run repeatedly on regular intervals. Over time, for example, a week, or a month, tests may be added or deleted. But generally, from one test interval to another, the tests that are run during the interval do not change. Examples of such scheduled software testing systems include wireless network end-to-end testers, and dialup internet service testers.
In a single interval (single run cycle time), the behavior of a scheduled test system can be described by a general class of mathematical problems known as Job Shop Scheduling Problems (JSSPs). This class of problems deals with optimizing machine use in a job shop. In the mathematical analogy, a job shop contains a set of specialized machines that each complete part of a job. Each type of job entering the shop is required to go through a series of operations unique to the type of job. In other words, each type of job requires use of a subset of the specialized machines to complete the job. The problem of creating an optimized schedule for all jobs entering the shop is called the Job Shop Scheduling Problem (JSSP).
Genetic algorithms (GA), also called ‘Evolutionary Algorithms’ (EA), are a class of mathematical algorithms that are popularly used to approximate optimized solutions to JSSPs. Genetic algorithms use principles of ‘genetic evolution’, by first creating a relatively small (typically hundreds) number of schedules, purely randomly. Next, the best schedules from this ‘population’ are given a chance to ‘recombine’ to create the next ‘generation’ of schedules. Every ‘generation’ of schedules also undergoes random ‘mutation’ to create new ‘features’ not available in the current generation. If this process of selection, recombination, and mutation is repeated a sufficient number of times, for example, thousands of times, taking care to ‘breed’ the best schedules, the overall population will ‘evolve’ towards better schedules.
In a conventional scheduled software testing system for a wireless network, a diagnostic measurement system submits a list of tests to be run during a testing interval to a test controller. For each submitted test, the test controller uses a scheduler to decide a time at which each test is to be started. The scheduler decides the time to start each test by using historical data of the amount of time each test required in previous testing intervals. Put differently, the more time a given test requires to complete, the more likely that the given test will be started early in the testing interval.
When a given test is scheduled to start, the test controller requests test resources (test objects) needed to run the given test from a resource manager. If the resources needed to run the given test are being used by some other test, the given test has to wait. When the resources become available, the test is allowed to start running on the test objects. The test objects are special purpose computers where the actual physical resources needed to run the test are located. A particular test object may have multiple resources, which may be required for different parts of a given test. Once a test is completed, test results are reported back from the test object to the test controller, which relays the test results back to the diagnostic management system (DMS).
The diagnostic management system is connected with a data store that stores results of previously run tests. Portions of this data are used by the diagnostic measurement system to create a baseline, or a prediction of the time each test is likely to take to complete, depending on a pattern each test has followed historically. The DMS uses the time taken by each test to create or improve the baseline data for each test.
The scheduler has a local memory, and stores the time taken by each test (elapsed test time) in the local memory. The elapsed test time includes any time the test may have spent waiting for the test resources. The scheduler uses this data when determining test start times for future testing intervals.
In this conventional scheduled software testing system for a wireless network, when the resource manager grants test resources for the test controller to run a given test, the resource manager secures all resources necessary for the given test, so that the given test can be completed without having to wait. Thus, the scheduled software testing system is required to use limited physical resources. In other words, even if the given test only uses a particular resource at the very beginning of the given test, that particular resource is secured by the resource manager until the given test is completed. In short, simultaneous test runs are not possible if the tests use the same resource.
To analogize this situation for the JSSP, two different jobs may both require use of a particular specialized machine, but only one job at a time can use the particular specialized machine. Additionally, once a job is started, all specialized machines required to complete that job are occupied until the job is complete. Thus, even if a first job is finished using one of the specialized machines, that specialized machine is not free for use by another job until the first job is complete.
In such a conventional scheduled software testing system, problems can arise. For example, when a scheduler only uses historical length of completion to determine test start times during a testing interval, length of completion for a given test will be skewed if the given test has to wait for a required test object to become available. In such a case, starting the test earlier in the testing interval will not yield a more efficient test schedule unless the required test object (resource) is available.
For example, assume both Test A and Test B require test object A, Test A is started at Time 1, and Test B is started at Time 2, which is prior to completion of Test A. Over several testing intervals, to improve the efficiency of the test schedule, the conventional scheduler will progressively move the start time of Test B closer to Time 1. The flaw in such a system is apparent: even if Test B is started immediately after Test A, Test B will not be able to run until Test A is finished, and Test B's length of completion will continue to increase. Even if the Test B were started prior to test A, while Test B's length of completion may improve, Test A's length of completion would increase.
Such problems increase as the number of tests and test devices increase. Additionally, as the number of tests and resources in each schedule increases, the number of possible schedules increases rapidly, and for test systems with limited physical resources, there is no available mathematical formula to simply calculate the best schedule from an initial list of tests. Further, since a typical wireless test system contains hundreds of devices and thousands of tests that use one or more devices at any given time, it would not be feasible, given the limitations in computer speed and memory, to go through all the possible schedules to decide on the best schedule within a reasonable time.
The conventional scheduled software testing system attempts to provide individual test schedules which does not account for the effect of limited test resources on tests sharing the resources. Additionally, the conventional scheduled software testing system does not provide an easy metric for device usage or the amount of improvement between schedules.
Further, the conventional scheduled software testing system is reactive. That is, no prior warning of potential conflicts of device usage is available. Wireless test systems are prone to expected, periodic overloads. While the baseline data provides a way to predict if system overload occurs at regular intervals, there is a possibility that the system may not be designed for peak capacity, or may be designed with too much slack to avoid potential overload. This would unnecessarily increase a cost of the system.